package 剑指offer;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

/**
 * 
 * @author ：soulstones
 * @version ：2019年9月30日 下午6:24:45 @Description：
 * 
 *          输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
 */
public class $3从头到尾打印链表 {
	
	//创建链表结点
public static class ListNode{
	int val;
	ListNode next;
	public ListNode() {
	}
	public ListNode(int  val) {
		this.val=val;
		this.next=null;
	}
}
	
//头插法创建链表
public  static ListNode creatListNode(ListNode listNode) {
	Scanner scanner = new Scanner(System.in);
	int val = scanner.nextInt();
	return listNode;
}
	
//输出打印链表
public static  void  printListNode(ListNode listNode) {
	ListNode next = listNode.next;
	while (next!=null) {
		System.out.println(next.val);
		next=next.next;
	}
}

public  static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

	ArrayList<Integer> list = new ArrayList<>();
	ListNode pre=null;
	ListNode next=null;
	while (listNode!=null) {
		next=listNode.next;
		listNode.next=pre;
		pre=listNode;
		listNode=next;
	}
	while (pre!=null) {
		list.add(pre.val);
		pre=pre.next;
	}
	return list;
}



//利用栈

public  static ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
	Stack<Integer> stack = new Stack<>();
	ArrayList<Integer> list = new ArrayList<>();
	ListNode node = listNode;
	while (node!=null) {
		stack.push(node.val);
		node=node.next;
	}
	while (!stack.empty()) {
		list.add(stack.pop());
	}
	return list;
}

}
